// package solution 解决方案相关题目
package solution

import "math"

// https://leetcode-cn.com/leetbook/read/top-interview-questions/xa7r55/
// https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/
// 可以在常数时间内获取到最小值的栈
// 算法: 在每次 push、pop 的时候更新最小值
// 时间复杂度: push O(1) pop O(n) getMin O(1)
// 更优解法: 最小值通过树 的结构存入
type MinStack struct {
	arr    []int
	minInt int
}

/** initialize your data structure here. */
func Constructor() MinStack {
	stack := MinStack{
		arr:    []int{},
		minInt: math.MaxInt64, // 题目保证了 getMin 一定会在有元素的时候执行
	}
	return stack
}

func (this *MinStack) Push(val int) {
	this.arr = append(this.arr, val)
	if this.minInt > val {
		this.minInt = val
	}
}

func (this *MinStack) Pop() {
	if len(this.arr) == 0 {
		return
	}
	toPopEle := this.arr[len(this.arr)-1]
	this.arr = this.arr[:len(this.arr)-1]
	if toPopEle == this.minInt {
		this.minInt = math.MaxInt64
		for _, currentVal := range this.arr {
			if this.minInt > currentVal {
				this.minInt = currentVal
			}
		}
	}
}

func (this *MinStack) Top() int {
	return this.arr[len(this.arr)-1]
}

func (this *MinStack) GetMin() int {
	return this.minInt
}
